The present invention generally relates to a method of processing information or data of a drawing and an apparatus for carrying out the same. More particularly, the invention is concerned with a method and an apparatus for extracting at a high speed a set of figures viewed in a designated rectangular region (referred to as a window) from a drawing of large scale such as a logic circuit design drawing and a mask pattern drawing for a very large scale integrated circuit (VLSI) and others, for thereby allowing the extracted figure data to be used for the edition of drawings later on.
As the techniques for extracting at a high speed a set or group of figures viewed in a designated window, there have heretofore been known a field block method and a bucket division method such as those described, for example, in Japanese patent unexamined publications, JP-A-60-163169, JP-A-61-150073, JP-A-61-241873, JP-A-62-80766, Japanese patent examined publication JP-61-26713 and T. Asano et al "Computational Geometry Algorithms" North-Holland, Advances in CAD for VLSI, Volume 4 (1986), pp. 307-308.
According to the field block method disclosed in JP-A-61-241873, a plurality of field block memory regions each of a predetermined fixed size are previously prepared, wherein figure data indicating given figures are sequentially stored at first in a first field block memory region. When the first field block memory region becomes full of the figure data, the succeeding figure data are then sequentially stored in a second field block memory region. When the second region is filled up, the storage of the figure data is then performed for the succeeding field block memory region. In this way, similar storage process is repeatedly carried out.
By way of example, reference is to be made to FIG. 1 of the accompanying drawings. The figure data of a FIG. 1 indicated by a hatched area contains position data of a rectangle 2 which can cover or encompass this FIG. 1 with a minimum area (which rectangle is referred to as a figure covering rectangle), and shape data concerning the shape or profile of the FIG. 1. The position data of the figure covering rectangle 2 are given in terms of the coordinates (E1, E2) of a bottom leftmost point a of that rectangle and the coordinate (E3, E4) of a top rightmost point e thereof, while the shape data includes the coordinates of individual discontinuity points or inflection points a, b, c, d, e, f, g and h as well as other data concerning the shape of the FIG. 1. Accordingly, of the figure data for given figures, the amount of the shape data may differ from one to another figure in dependence on the shapes or geometries thereof, even when the position data can remain constant. Suppose, for example, a drawing illustrating thereon a plurality of figures covered by rectangles g1 to g8, respectively, as is shown in FIG. 2 of the accompanying drawings. These rectangles g1 to g8 are to be stored in this order in the field block memory regions FB1 to FB4 in such a manner as shown in FIG. 3A. In that case, the figure data of the figure covering rectangles g1 and g2 are stored in the field block memory region FB1, the figure data of the figure covering rectangles g3 and g4 are stored in the field block memory region FB2, the figure data of the figure covering rectangles g5 and g6 are stored in the field block memory region FB3, and finally the figure data of the figure covering rectangles g7 and g8 are stored in the field block memory region FB4. Since the amount of the shape data contained in the figure data may differ in dependence on the shape or geometry of the figure encompassed by the figure covering rectangle, as described above, the individual field block memory regions can not always store the figure data for a same number of the figure covering rectangles as in the case of the abovementioned example. In other words, the number of the figure covering rectangles whose figure data are stored in given ones of the field block memory regions can not be constant. Besides, the number of the field block memory regions to be used will vary in dependence on the scale of the drawing to be processed, i.e. the total number of the figures illustrated on the drawing and the shapes of the individual figures.
Further, for storing information or data for managing the field block memory regions, there is provided a managing memory having memory regions allocated in correspondence to the field block memory regions, respectively, as is shown in FIG. 3B. In this case, a rectangle capable of covering with a minimum area all the figure covering rectangles which stored in a given field block memory region is referred to as a field block, wherein the position data indicating the position of the field block, e.g. the coordinates of the bottom leftmost and the top rightmost points of the field block are stored in the region of the managing memory which corresponds to that given one field block memory region. In the case of the example shown in FIG. 2, the field block memory region including the figure covering rectangles g1 and g2 constitutes a field block indicated by a broken-line rectangle FB1. The field blocks FB2, FB3 and FB4 are defined in similar manner. FIG. 4 shows only the field blocks extracted from the illustration shown in FIG. 2. The position data of the field block FB1, by way of example, are given in terms of the coordinates P1, P2 of the bottom leftmost point of that block and the coordinates P3, P4 of the top rightmost point thereof and stored in the region of the managing memory corresponding to the field block memory region FB1. Similarly, the position data of the field blocks FB2, FB3 and FB4 are stored in the corresponding regions of the managing memory, respectively, as shown in FIG. 3B.
Next, referring to FIG. 5, description will be made of a procedure for extracting those figures which is viewed in or overlaps with a designated window such as, for example, a window 9 from a number of figures stored in a number of the field block memory regions. It should however be understood that for the sake of simplification of the description, the number and the positions of the figure covering rectangles and the field blocks shown in FIG. 5 bear no relation to those illustrated in FIG. 4. Now, referring to FIG. 5, the figure viewed in the window 9 is extracted through the procedure steps mentioned below. Step 1: The position data of the given window 9 represented by the coordinates (W1, W2) of the bottom leftmost point and the coordinates (W3, W4) of the top rightmost point are compared with the position data of the individual field blocks stored in the managing memory, whereby all the field blocks overlapping with the window 9 are extracted. In the case of the example illustrated in FIG. 5, one field block 5 is extracted. Step 2: The position data of the figure covering rectangles included in each of the extracted field blocks are read out from the associated field block memory regions to be compared with the position data of the abovementioned window 9, to thereby extract all the figure covering rectangles overlapping with the window 9. In the case of the example shown in FIG. 5, only the figure covering rectangle g2 is extracted from the rectangles (g1, g2 and g3) that are included in the field block 5. Step 3: The shape data of the figure included in the extracted figure covering rectangle g2 is compared with the position data of the window to thereby extract the figure included in the window.
Next, consideration will be paid to the time involved in executing the calculations for extracting the figure covering rectangle viewed in the designated window.
It is assumed that N represents the number of the field blocks, n represents the number of all the figures included in a drawing, m represents the number of the field blocks overlapping with the window, T.sub.1.sup.2 represents the time involved in the calculation for extracting the field blocks overlapping with window, T.sub.2.sup.2 represents the time involved in calculation for extracting the figure covering rectangle overlapping with the window from each of the extracted field block, and T.sup.2 represents the time in total involved in all the calculations. Then, T.sub.1.sup.2 and T.sub.2.sup.2 can be given by the following expressions (1) and (2): ##EQU1## on the assumption that each of the field block memory regions stores a same number (n/N) of the figures. The processing for extracting the field block overlapping with the window and the processing for extracting the figure covering rectangle overlapping with the window are both executed by repeating the step of checking whether two rectangles overlap each other. In this connection, t.sub.o appearing in the above expressions (1) and (2) represents the time required for the processing of this one step.
From the expressions (1) and (2), ##EQU2## On the condition that scale of the drawing to be processed, i.e. n is constant, there exists such value of N which can minimize the time T.sup.2. In this conjunction, n/N may be regarded to represent the size of the field block memory. Thus, it can be said that there exists the size of the field block memory which is optimal for minimizing the time T.sup.2. According to the field block method known heretofore, however, the size of the field block memory region is fixed independent of the scale of the drawing to be processed as described hereinbefore. Consequently, there can not always be obtained the minimum time (i.e. maximum processing speed) for extracting the figure associated with the window, although it depends on the scale of the drawings.
Generally speaking, however, the figure extraction based on the field block method is still advantageous in that only a small amount of information is sufficient for the managing purpose, and that when the figure is altered, it is sufficient to alter the managing information only for such field block whose region including the figure of concern needs to be correspondingly altered, whereby the procedure for updating the managing information can be extremely simplified.
Now, description will be turned to the bucket division method. According to this method, a drawing is previously divided into a plurality of rectangular regions each of a same size referred to as the buckets, as is shown in FIG. 6 of the accompanying drawings, wherein the figures existing within the buckets are stored in a managing table on the bucket basis. In the example shown in FIG. 6, the drawing is divided into four buckets B1, B2, B3 and B4, and the regions in the managing table stored in a memory are correspondingly allocated to the buckets, respectively, as is shown in FIG. 7A. More specifically, the region B1 of the managing table memory stores the figure data of the figure covering rectangles g1 and g8 which are at least partially included in the bucket B1, while the region B2 stores therein the figure data of the figure covering rectangle g4 and g5 included at least partially in the bucket B2. Further, the region B3 of the managing table memory stores the figure data of the figure covering rectangles g3 and g6 included at least partially in the bucket B3. The region B4 stores the figure data of figure covering rectangles g2, g7 and g5 included at least partially in the bucket B4.
For extracting the figures overlapping with a designated window from the figure data stored in the managing table in the manner mentioned above, the bucket overlapping with the window is first extracted, being then followed by extraction of the figure covering rectangle viewed in the window from those included in each of the extracted buckets. Thereafter, the desired figure is determined from the extracted figure covering rectangle.
The bucket division method outlined above requires significant alternation or modification of the contents of the managing table, when the figure is to be moved or migrated. By way of example, in case the figure covering rectangle g3 is migrated from a solid line position to a dotted line position, as illustrated in FIG. 6, the figure covering rectangles included in the buckets B1, B2 and B4 are changed. As the consequence, it is necessary to alter correspondingly the contents in the regions of the managing table which are allocated to the buckets B1, B2 and B3, as shown in FIG. 7B. Nevertheless of the shortcoming of the bucket division method mentioned above, this method is yet advantageous in that extraction of the figures overlapping with the window can be performed with high efficiency by virtue of the capability of classifying the figures located close to one another in a group on the bucket basis.